package maze.model.astar;

import java.util.ArrayList;
import java.util.List;
import maze.model.MazeMap;
import maze.pojo.Action;
import maze.pojo.Point;
import maze.utils.PointPool;

/**
 * @author Shiba Yumeno
 *
 */
public class PathFinder {

	private MazeMap maze;

	private OpenList openList;

	private MapNode mapTable[][];

	private PointPool pool;

	public PathFinder(MazeMap maze) {
		super();
		this.maze = maze;
	}

	public List<Point> findPath(Point start, Point dst) {
		init();
		start = pool.get(start);
		dst = pool.get(dst);
		mapTable[dst.x][dst.y].cost = 1;
		openList.offer(dst, 0);
		while (!openList.isEmpty()) {
			Point node = openList.poll();
			if (node == start) {
				break;
			}
			int moveable = maze.getPossibleActions(node);
			Point next;
			if ((moveable & Action.LEFT.bit) > 0) {
				next = pool.move(node, Action.LEFT);
				move(node, next, dst);
			}
			if ((moveable & Action.RIGHT.bit) > 0) {
				next = pool.move(node, Action.RIGHT);
				move(node, next, dst);
			}
			if ((moveable & Action.UP.bit) > 0) {
				next = pool.move(node, Action.UP);
				move(node, next, dst);
			}
			if ((moveable & Action.DOWN.bit) > 0) {
				next = pool.move(node, Action.DOWN);
				move(node, next, dst);
			}
		}
		ArrayList<Point> list = new ArrayList<>();
		Point p = start;
		do {
			list.add(pool.get(p));
		} while ((p = mapTable[p.x][p.y].next) != dst);
		list.add(dst);
		return list;
	}

	private void init() {
		openList = new OpenList();
		int w = maze.getWidth();
		int h = maze.getHeight();
		pool = PointPool.getPool();
		mapTable = new MapNode[w][h];
		for (int x = 0; x < w; x++) {
			for (int y = 0; y < h; y++) {
				mapTable[x][y] = new MapNode();
			}
		}

	}

	private void move(Point node, Point next, Point dst) {
		if (mapTable[next.x][next.y].cost == 0) {
			mapTable[next.x][next.y].cost = mapTable[node.x][node.y].cost + 1;
			int score = mapTable[next.x][next.y].cost
					+ Point.distance(next, dst);
			mapTable[next.x][next.y].next = node;
			openList.offer(next, score);
		}
	}
}

class MapNode {
	int cost;
	Point next;

	public MapNode() {
		cost = 0;
	}
}
